#pragma once
#include "DynArray.h"
#include "SLList.h"
#include <queue>
template <typename Type> class Graph
{

public:
	struct Edge
	{
		unsigned int toVertex;
	};
	struct Vertex
	{
		Type element;
		SLList<Edge> edges;
		void addEdge(const unsigned int& toVertrex);
	};
private:
	DynArray<Vertex> arr;
public:
	unsigned int addVertex(const Type& value);
	Vertex& operator[](const unsigned int& index);
	unsigned int size() const;
	void clear();
	void printBreadthFirst(const unsigned int& startVertex);
};
template<typename Type>
void typename Graph<Type>::Vertex::addEdge(const unsigned int& toVertrex)
{
	Edge e;
	e.toVertex = toVertrex;
	edges.addHead(e);
}


template<typename Type>
unsigned int Graph<Type>::addVertex(const Type& value)
{
	Vertex a;
	a.element = value;
	arr.append(a);
	return arr.size() - 1;
}

template<typename Type>
typename Graph<Type>::Vertex& Graph<Type>::operator[](const unsigned int& index)
{
	return arr[index];
}

template<typename Type>
unsigned int Graph<Type>::size() const
{
	return arr.size();
}

template<typename Type>
void Graph<Type>::clear()
{
	arr.clear();
}

template<typename Type>
void Graph<Type>::printBreadthFirst(const unsigned int& startVertex)
{
	queue<unsigned int> s;
	unsigned int v = startVertex;
	int *exp = new int[arr.size()];
	int depth = 0;
	for (decltype(arr.size()) i = 0; i < arr.size(); i++)
		exp[i] = -1;
	s.push(v);
	exp[v] = depth;
	while(!s.empty())
	{
		depth = s.front();
		s.pop();
		SLLIter<Graph<Type>::Edge> j(arr[depth].edges);
		for (j.begin(); !j.end(); ++j)
		{
			if(exp[j.current().toVertex] == -1)
			{
				s.push(j.current().toVertex);
				exp[j.current().toVertex] = exp[depth] + 1;
			}
		}
	//	if(startVertex != v)
	//	{
	//		depth += v;
	//	}
		cout << arr[depth].element << " : " << exp[depth] << "\n";
	}
	delete [] exp;
}
